//#include"Heap.h"
//
////初始化
//void HeapInit(HP* php)
//{
//  assert(php);
//
//  php->a = nullptr;
//  php->size = php->capacity = 0;
//}
//
////销毁
//void HeapDestroy(HP*php)
//{
//  assert(php);
//
//  delete[] php->a;
//  php->a = nullptr;
//  php->size = php->capacity = 0;
//}
//
//void swap(HPDataType& child, HPDataType& parent)
//{
//  HPDataType tmp = child;
//  child = parent;
//  parent = tmp;
//}
//
////向上调整算法———建小堆
//void AdjustUp(HPDataType* php, size_t child)
//{
//  assert(php);
//
//  size_t parent = (child - 1) / 2;
//  while(child > 0)
//  {
//    if(php->a[child] < php->a[parent])
//    {
//      swap(php->a[child], php->a[parent]);
//      child = parent;
//      parent = (child - 1) / 2;
//    }
//    else{
//      break;
//    }
//  }
//}
//
//
////插入
//void HeapPush(HP* php, HPDataType x)
//{
//  assert(php);
//
//  if(php->size == php->capacity)
//  {
//    size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
//    HPDataType* tmp=(HPDataType*)realloc(php->a,sizeof(HPDataType)*newCapacity);
//    assert(tmp);
//    php->a = tmp;
//    php->capacity = newCapacity;
//  }
//  php->a[php->size] = x;
//  php->size++;
//
//  //向上调整，控制保持是一个小堆
//  AdjustUp(php->a, php->size - 1);
//
//}
//
////打印
//void HeapPrint(php-)


#include"Heap.h"


//向上调整算法
void AdjustUp(HPDataType* php, size_t child);



namespace sl
{
    // 建大堆
    template<class T>
    struct less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    // 建小堆
    template<class T> 
    struct greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };

    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    private:
        Container _con; // 底层容器
        Compare _comp; // 比较规则

    public:
        // 向上调整
        void adjustup(int child)
        {
            int parent = (child - 1) / 2;

            while(child > 0)
            {
                if(_comp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        // 向下调整
        void adjustDown(int n, int parent)
        {
            int child = parent * 2 + 1;

            while(child < n)
            {
                // 比较左右孩子
                if(child + 1 < n && _comp(_con[child], _con[child + 1]))
                    child++;

                // 比较父亲和孩子
                if(_comp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        // 向堆中插入数据
        void push(const T& val)
        {
            _con.push_back(val);
            adjustup(_con.size() - 1);
        }

        // 弹出堆顶数据
        void pop()
        {
            std::swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjustDown(_con.size(), 0);
        }

        // 读取堆顶数据
        T& top()
        {
            return _con[0];
        }

        const T& top() const
        {
            return _con[0];
        }

        int size() const
        {
            return _con.size();
        }

        bool empty() const
        {
            return _con.empty();
        }
    };  
}

namespace sl
{
    // 建大堆
    template<class T>
    struct less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    // 建小堆
    template<class T>
    struct greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };


    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    private:
        Container _con; // 底层容器
        Compare _comp; // 比较规则

    public:
        // 向上调整
        void adjustUp(int child)
        {
            int parent = (child - 1) / 2;

            while(child > 0)
            {
                if(_comp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        // 向下调整
        void adjustDown(int n, int parent)
        {
            int child = parent * 2 + 1;

            while(child < n)
            {
                if(child + 1 < n && _comp(_con[child], _con[child + 1]))
                    child++;

                if(_comp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        // 向堆中插入元素
        void push(const T& val)
        {
            _con.push_back(val);
            adjustUp(_con.size() - 1);
        }

        // 弹出堆顶元素
        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjustDown(_con.size(), 0);
        }

        // 读取堆顶元素
        T& top()
        {
            return _con[0];
        }

        const T& top() const
        {
            return _con[0];
        }

        bool empty() const
        {
            return _con.empty();
        }

        int size() const
        {
            return _con.size();
        }
    };  
}



{
    // 建大堆
    template<class T>
    struct less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    // 建小堆
    template<class T>
    struct greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };

    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    private:
        Container _con; // 底层容器
        Compare _comp; // 比较规则

    public:
        // 向上调整
        void adjustUp(int child)
        {
            int parent = (child - 1) / 2;

            while(child > 0)
            {
                if(_comp(_con[parent], _con[child]))
                {
                    std::swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        // 向下调整
        void adjustDown(int n, int parent)
        {
            int child = parent * 2 + 1; // 默认是左孩子

            while(child < n)
            {
                if(child + 1 < n && _comp(_con[child], _con[child + 1]))
                    child++;

                if(_comp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        // 向堆中插入元素
        void push(const T& val)
        {
            _con.push_back(val);
            adjustUp(_con.size() - 1);
        }

        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjustDown(_con.size(), 0);
        }

        T& top()
        {
            return _con[0];
        }

        const T& top() const
        {
            return _con[0];
        }

        int size() const
        {
            return _con.size();
        }

        bool empty() const
        {
            return _con.empty();
        }


    };
}



